package Classic150;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class 查找和最小的K对数字 {
    /*
        https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/solutions/2286318/jiang-qing-chu-wei-shi-yao-yi-kai-shi-ya-i0dj
     */
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{nums1[0] + nums2[0], 0 , 0});
        while (res.size() < k) {
            int[] comb = pq.poll();
            int i = comb[1];
            int j = comb[2];
            res.add(List.of(nums1[i], nums2[j]));
            if (j == 0 && i + 1 < nums1.length) pq.offer(new int[]{nums1[i + 1] + nums2[0], i + 1, 0});
            if (j + 1 < nums2.length) pq.offer(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
        }
        return  res;
    }
}
